1. Field of the Invention
The present invention relates to an undeniable digital signature scheme which is a type of digital signature that can protect a privacy of a signer.
2. Description of the Background Art
In electronic communications, the digital signature technology is effective in checking the validity of data. The most widely used digital signature is the RSA signature that utilizes modular exponentiation calculations (see R. Rivest, A. Shamir and L. M. Adleman, “A method for obtaining digital signatures and public key cryptosystems”, Communications of ACM, 21(2), pp. 120–126, 1978).
A digital signature scheme is evaluated by its security and its signature generation/verification speed, so that a digital signature scheme with a higher security and a faster computation speed is considered as superior. The security of the RSA signature is based on the intractability to compute the secret keys from public keys. A more secure system can be realized by making the key length of the public key longer. The RSA signature involves the modular exponentiation calculations that have great computational complexity so that there has been a drawback that the signature generation/verification requires a considerable amount of time.
As a variation of the digital signature, there has been a proposition of an undeniable signature (see D. Chaum and H. van Antwerpen, “Undeniable Signatures”, Advances in Crypttology—CRTPTO'89, LNCS 435, pp. 212–216, Springer-Verlag, 1990). In the undeniable signature scheme, the legitimacy of the signature cannot be verified without communicating with a signer, so that the signature can be traced and the privacy of the signer can be protected. A standard application of the undeniable signature is a secure distribution of software, where a purchaser of the software can make a contact with a distributor who is also a signer and check that the software does not contain a virus entered by a third person.
The most efficient undeniable signature scheme to date is the RSA-based undeniable signatures (see R. Gennaro, H. Krawczyk and T. Rabin, “RSA-Based Undeniable Signatures”, Advances in Cryptology—CRYPTO '89, LNCS 435, pp. 212–216, Springer-Verlag, 1990). This scheme is based on the RSA signature so that it is also associated with the problem of a large computational complexity.
In this regard, a smartcard has been attracting much attentions lately as an easily portable device for storing secret keys securely. However, a smartcard has limited computational resources so that a considerable time would be required to execute the RSA-based undeniable signature scheme on a smartcard. Moreover, in the case of using the undeniable signatures in a large scale information distribution system, there arises a problem of overloading the server. For these reasons, there has been demands for an efficient and high speed undeniable signature scheme.